package com.hfb.mashibing.alip8.diamondsquarealgorithm.class01;

import java.util.LinkedList;

/**
 * 算法：滑动窗口
 *
 * 问题简述：获取滑动窗口，在滑动时每一次的最大值
 * 【问题详述】
 * 有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次 向右边滑一个位置。
 * 例如，数组为[4,3,5,4,3,3,6,7]，窗口大小为3时:
 * [4 3 5]4 3 3 6 7 窗口中最大值为5
 * 4[3 5 4]3 3 6 7  窗口中最大值为5
 * 4 3[5 4 3]3 6 7  窗口中最大值为5
 * 4 3 5[4 3 3]6 7  窗口中最大值为4
 * 4 3 5 4[3 3 6]7  窗口中最大值为6
 * 4 3 5 4 3[3 6 7] 窗口中最大值为7
 * 如果数组长度为n，窗口大小为w，则一共产生n-w+1个窗口的最大值。
 *
 * 请实现一个函数。
 * 输入:整型数组arr，窗口大小为w。
 * 输出:一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下的最大值，
 * 以本题为例，结果应该返回{5,5,5,4,6,7}。
 *
 *
 * 【思路】
 * 迅速得到窗口内的最大值：
 * 使用一个双端队列，双端队列严格按照从大到小排。
 *
 * 数据增加：
 * 若增加的数从尾进，若增加的数可以放在尾部，则放入，若无法放入，则将尾部数弹出，直到增加的数可以从尾部进入。
 * 数据减少：
 * 若过期的数的位置是双端队列的头部，则过期的数从头部弹出，若不是头部，则不弹出。
 * 滑动窗口概述
 * 【滑动窗口】
 * 滑动窗口模式是用于在给定数组或链表的特定窗口大小上执行所需的操作，比如寻找包含所有 1 的最长子数组。
 * 从第一个元素开始滑动窗口并逐个元素地向右滑，并根据你所求解的问题调整窗口的长度。
 * 在某些情况下窗口大小会保持恒定，在其它情况下窗口大小会增大或减小。
 *
 *
 *
 * 下面是一些你可以用来确定给定问题可能需要滑动窗口的方法：
 *
 * 问题的输入是一种线性数据结构，比如链表、数组或字符串
 * 要求查找最长/最短的子字符串、子数组或所需的值
 * 你可以使用滑动窗口模式处理的常见问题：
 * 1）大小为 K 的子数组的最大和（简单）
 * 2）带有 K 个不同字符的最长子字符串（中等）
 * 3）寻找字符相同但排序不一样的字符串（困难）
 *
 */
public class Code01_SlidingWindowMaxArray {
    public static class WindowMax{
        private int L;
        private int R;
        private int[] arr; // arr[   [L..R)     ]
        private LinkedList<Integer> qmax;

        public WindowMax(int[] a) {
            arr = a;
            L = -1;
            R = 0;
            qmax = new LinkedList<>();
        }

        //L = -1
        // R = 0
        // arr   [-1,1)
        //[ 3,2,1,4,5   ]
        // 0
        // [0,1)  arr[0]
        // 1
        // [-1,2)  arr[0,1]
        public void addNumFromRight() {
            if(R == arr.length) {
                return;
            }
            while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]) {
                qmax.pollLast();
            }
            qmax.addLast(R);
            R++;
        }

        // arr  [L,R)
        public void removeNumFromLeft() {
            if(L >= R-1) {
                return;
            }
            L++;
            if(qmax.peekFirst() == L) {
                qmax.pollFirst();
            }
        }

        public Integer getMax() {
            if(!qmax.isEmpty()) {
                return arr[qmax.peekFirst()];
            }
            return null;
        }
    }


    public static int[] getMaxWindow(int[] arr, int w) {
        if (arr == null || w < 1 || arr.length < w) {
            return null;
        }
        // 下标      值   大 -> 小
        LinkedList<Integer> qmax = new LinkedList<Integer>();
        int[] res = new int[arr.length - w + 1];
        int index = 0;
        for (int i = 0; i < arr.length; i++) { // 窗口（刚才讲的）的R
            // i -> arr[i]
            while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]) {//同理>=可以得到最小值
                qmax.pollLast();
            }
            qmax.addLast(i);
            if (qmax.peekFirst() == i - w) { // i - w  过期的下标
                qmax.pollFirst();
            }
            if (i >= w - 1) { // 窗口形成了
                res[index++] = arr[qmax.peekFirst()];
            }
        }
        return res;
    }
}
